#include "ac.greedy.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int maxSubArray(int *nums, int numsSize)
{

    if (numsSize == 0) {
        return 0;
    }

    int i;

    int *tmp = (int *)malloc(sizeof(int) * numsSize);
    memset(tmp, 0, numsSize);
    tmp[0] = nums[0];

    for (i = 1; i < numsSize; i++) {
        tmp[i] = nums[i] + (tmp[i - 1] > 0 ? tmp[i - 1] : 0);
    }

    int max = -(1 << 20);
    for (i = 0; i < numsSize; i++) {
        max = tmp[i] > max ? tmp[i] : max;
    }
    free(tmp);
    return max;
}
